package string;

/**
 * 5.最长回文串 Longest Palindromic SubString
 *
 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

 Example 1:

 Input: "babad"
 Output: "bab"
 Note: "aba" is also a valid answer.
 Example 2:

 Input: "cbbd"
 Output: "bb"
 */
public class Q5_LongestPalindrome {
    /**
     * expanding the center to both sides
     */
    private String longestPalindrome(String str) {
        if (str==null || "".equals(str) || str.length() <= 1) {
            return str;
        }
        String resultStr = "";
        for (int i=0; i<str.length(); i++) {
            int len1 = expandAroundCenter(str, i, i);
            int len2 = expandAroundCenter(str, i, i+1);
            int len = len1 > len2? len1: len2;
            if (resultStr.length() < len) {
                /*
                例如：abccba len=6; abcba len=5;
                统一处理
                 1.截取中心（cc c）的左侧长度 (len - 1) / 2
                 2.i + len / 2
                 */
                int start = i - (len - 1) / 2;
                int end = len + i - (len - 1) / 2;//i+len/2;
                resultStr = str.substring(start, end);
            }
            //123456
        }
        return resultStr;
    }

    private int expandAroundCenter(String str, int midl, int midr) {
        while (midl >= 0 && midr < str.length()
                && str.charAt(midl) == str.charAt(midr)) {
            midl--;
            midr++;
        }
        return midr - midl - 1;
    }

    /**
     * dynamic programming
     * two-dimensional array
     */
    private String longestPalindromeDp(String s) {
        if (s==null || "".equals(s) || s.length() <= 1) {
            return s;
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i=0; i<s.length(); i++) {
            dp[i][i] = true;
        }
        int start = 0;
        int maxLen = 1;
        for (int j=1; j<s.length(); j++) {
            for (int i=0; i<j; i++) {
                if (s.charAt(j) == s.charAt(i)) {
                    if ((j-1)-(i+1)+1 <= 1) {//单字母
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if (dp[i][j]) {
                    int curLen = j - i + 1;
                    if (curLen > maxLen) {
                        start = i;
                        maxLen = curLen;
                    }
                }
            }
        }
        /*
    0 1 2 3 j //abac dp[i][j] is the length of a palindrome whose index is from i to j.
  0 t f t f   // state: dp[i][j]
  1 f t f f   // state transfer equation: dp[i][j] = dp[i+1][j-1]+1
  2 f f t f
  3 f f f t
  i
         */
        return s.substring(start, start+maxLen);
    }

    /**
     * Compare with the reversed string by using dynamic programming
     */
    private String longestPalindromeReverseDp(String s) {
        if (s==null || "".equals(s) || s.length() <= 1) {
            return s;
        }
        String reverse = new StringBuilder(s).reverse().toString();
        int[][] dp = new int[s.length()][s.length()];
        int maxLen = 1;
        int stat = 0;
        for (int i=0; i<s.length(); i++) { //reverse
            for (int j=0; j<s.length(); j++) { //origin
                if (reverse.charAt(i) == s.charAt(j)) {
                    if (i==0 || j==0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i-1][j-1]+1;
                    }
                }
                if (dp[i][j] > maxLen) {
                    //maybe appear “abc12cba" and "abc21abc",
                    //causing the result is "abc",
                    //but the result is not correct.
                    //Therefore, add judging conditions that are to compare the letter's position
                    int originEnd = i - dp[i][j] + 1;//due to the "i" represents reversing string
                    int originStat = s.length() - i;
                    if (originEnd == j) { // the "j" represents original string
                        System.out.println("comparing the difference between the reversed string and the origin string:"+originEnd+" "+j);
                        maxLen = dp[i][j];
                        stat = i - maxLen + 1;//the beginning index of the reverse string
                    }

                }
            }
        }
        /*
        a b a a c j origin
      c 0 0 0 0 1  // maxLen = 3; end = i = 4; stat = end-maxLen+1
      a 1 0 1 1 0  // substring(stat, stat+end)
      a 1 0 1 2 0  // end需要以外层循环的为准
      b 0 2 0 0 0
      a 1 0 3 1 0
      i
      reverse
         */
        for (int i=0; i<s.length(); i++) {
            for (int j=0; j<s.length(); j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(stat+" "+maxLen);
        return reverse.substring(stat, stat+maxLen);
    }

    public static void main(String[] args) {
        Q5_LongestPalindrome q5_longestPalindrome = new Q5_LongestPalindrome();
        String str = "abaac"; //abc12cba
        System.out.println(q5_longestPalindrome.longestPalindrome(str));
        System.out.println(q5_longestPalindrome.longestPalindromeDp(str));
        System.out.println(q5_longestPalindrome.longestPalindromeReverseDp(str));
    }
}
